package com.notes.algo.exam;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.Map;

/**
 * @author
 * @Describe 设计一个程序，其从标准输入接收原点、目的点编号以及描述连通性的边的集合，向标准输出从原点出发到目的节点的最短路径，不可达则输出0。
 * @date
 */
public class Solution5 {
    public static void main(String[] args) {
        String disPath = dijkstra("1", "3", "1-4,1-6,2-4,2-6,3-5,3-6,4-5,5-6");
        System.out.println(disPath);
    }

    public static String dijkstra(String begin, String end, String edgesStr) {
        // 所有节点
        java.util.Set<String> allNodeSet = new java.util.HashSet<String>();
        // 连通性边集合
        java.util.List<java.util.Map<String, String>> edgeList = new ArrayList<>();
        // 当前节点可达节点路径列表
        java.util.List<Map<String, String>> pathList = new ArrayList<>();
        // 开始节点到指定节点的距离
        java.util.Map<String, Integer> nodePathMap = new HashMap<>();
        // 到达当前节点前驱结点信息，用于反向查找中间节点路径数据
        java.util.Map<String, Map<String, String>> minPathMap = new HashMap<>();

        // 获取所有的节点及边集合数据
        String[] edgeArr = edgesStr.split(",", -1);
        for (int i = 0; i < edgeArr.length; i++) {
            String curEdge = edgeArr[i];
            String[] curEdgeInfo = curEdge.split("-");
            String edgeStart = curEdgeInfo[0];
            String edgeEnd = curEdgeInfo[1];
            allNodeSet.add(edgeStart);
            allNodeSet.add(edgeEnd);
            java.util.Map<String, String> edgeNode = new HashMap<>();
            edgeNode.put("edgeStart", edgeStart);
            edgeNode.put("edgeEnd", edgeEnd);
            edgeNode.put("edgeLen", "1");
            edgeList.add(edgeNode);
            // 反向也作为一个边节点
            java.util.Map<String, String> edgeNodeOpp = new HashMap<>();
            edgeNodeOpp.put("edgeStart", edgeEnd);
            edgeNodeOpp.put("edgeEnd", edgeStart);
            edgeNodeOpp.put("edgeLen", "1");
            edgeList.add(edgeNodeOpp);
        }
        // 初始化开始节点等
        java.util.Map<String, String> beginNode = new HashMap<>();
        beginNode.put("pre", begin);
        beginNode.put("end", begin);
        beginNode.put("len", "0");
        // 加入可达节点路径
        pathList.add(beginNode);
        // 开始到开始的路径的距离
        nodePathMap.put(begin, 0);
        for (String nodeName : allNodeSet) {
            minPathMap.put(nodeName, null);
        }

        // 遍历可达节点数据处理 直到不存在可达节点
        while (pathList.size() > 0) {
            // 获取并移除第一个元素
            java.util.Map<String, String> curNode = pathList.remove(0);
            // 当前可达节点
            String endNodeName = curNode.get("end");
            // 开始节点到当前可达节点的最短距离
            Integer len = Integer.valueOf(curNode.get("len"));
            // 记录开始节点到到达当前节点的长度
            nodePathMap.put(endNodeName, len);
            // 记录到达当前节点的前驱结点路径关系
            minPathMap.put(endNodeName, curNode);

            // 遍历所有的边
            for (int i = 0; i < edgeList.size(); i++) {
                Map<String, String> curEdge = edgeList.get(i);
                // 边的开始节点
                String curEdgeStart = curEdge.get("edgeStart");
                // 找出以当前节点为开始节点的边，即开始节点为当前边的开始节点
                if (curEdgeStart.equals(endNodeName)) {
                    // 边的结束节点
                    String curEdgeEnd = curEdge.get("edgeEnd");
                    // 边的长度
                    Integer curEdgeLen = Integer.valueOf(curEdge.get("edgeLen"));
                    // 获取开始节点到当前边结束节点的距离
                    Integer begin2EdgeEndLen = nodePathMap.get(curEdgeEnd);
                    // 计算开始节点到当前可达节点的最短路径
                    if (begin2EdgeEndLen == null || begin2EdgeEndLen > len + curEdgeLen) {
                        java.util.Map<String, String> edgeNode = new HashMap<>();
                        edgeNode.put("pre", endNodeName);
                        edgeNode.put("end", curEdgeEnd);
                        edgeNode.put("len", len + curEdgeLen + "");
                        // 加入可达路径列表
                        pathList.add(edgeNode);
                        // 记录开始节点到当前可达节点的最小距离
                        nodePathMap.put(curEdgeEnd, len + curEdgeLen);
                    }
                }
            }
        }
        // 不可达输出0
        if (nodePathMap.get(end) == null) {
            return "0";
        }

        // 结束节点的最短路径信息
        Map<String, String> endNodeMap = minPathMap.get(end);
        // 结束节点的前驱结点
        String endNodePreNode = endNodeMap.get("pre");
        // 反向节点路径
        String pathStr = end;
        // 循环获取到前驱结点不是开始节点的数据
        while (!begin.equals(endNodePreNode)) {
            // 当前节点的前驱结点
            String curPathNode = minPathMap.get(endNodePreNode).get("end");
            endNodePreNode = minPathMap.get(endNodePreNode).get("pre");
            pathStr = pathStr + " " + curPathNode;
        }

        pathStr = pathStr + " " + begin;
        return pathStr;
    }
}
